#include <bits/stdc++.h>
using namespace std;
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
using ll = long long;

void solve()
{
    string s;
    string k;
    cin >> s >> k;

    if (k.size()>=3)
    {
        set<char> s_c;
        for (auto ch : s)
        {
            s_c.insert(ch);
        }
        cout << s_c.size() << endl;
    }
    else
    {
        ll kk;
        // 重复字符串 k 次
        string repeated_s;
        kk = stoi(k);
        for (int i = 0; i < kk; ++i)
        {
            repeated_s += s;
        }

        // 计算最长递增子序列的长度
        vector<int> dp(repeated_s.size(), 1);
        int max_len = 1;
        for (int i = 1; i < repeated_s.size(); ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (repeated_s[i] > repeated_s[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_len = max(max_len, dp[i]);
        }

        cout << max_len << endl;
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}